package org.hot100_0.leetcode31;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution2 {

    public static void main(String[] args) {
        int [] nums = {1,1,5};
        nextPermutation(nums);
        for (int num :nums) {
            System.out.println(num);
        }
    }

    public static void nextPermutation(int[] nums) {

        if (nums.length==1){
            return;
        }

        int slow = 0;
        int fast = 1;

        while (fast<nums.length){
            if (nums[fast]>nums[slow]){
                // 不是递增的
                backtracking(nums);
                List<Integer> list = res.get(1);
                for (int i = 0; i < nums.length; i++) {
                    nums[i]=list.get(i);
                }
                return;
            }
            fast++;
            slow++;
        }

        //是递增的，直接进行排序操作，得到值是最小值
        Arrays.sort(nums);
    }

   static List<List<Integer>> res = new ArrayList<>();
    static  List<Integer> item = new ArrayList<>();
    private static void backtracking(int [] nums){

        if (res.size()==2){
            return;
        }

        if (item.size()==nums.length){
            res.add(new ArrayList<>(item));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!item.contains(nums[i])){
                item.add(nums[i]);
                backtracking(nums);
                item.remove(item.size()-1);
            }
        }
    }
}
